package mine.code.day.year2021.month08;

import org.junit.Test;

import java.util.Arrays;

/**
 * 这里有n个航班，它们分别从 1 到 n 进行编号。
 * <p>
 * 有一份航班预订表bookings ，表中第i条预订记录bookings[i] = [firsti, lasti, seatsi]意味着在从 firsti到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi个座位。
 * <p>
 * 请你返回一个长度为 n 的数组answer，里面的元素是每个航班预定的座位总数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
 * 输出：[10,55,45,25,25]
 * 解释：
 * <p>
 * 航班编号        1   2   3   4   5
 * <p>
 * 预订记录 1 ：   10  10
 * <p>
 * 预订记录 2 ：       20  20
 * <p>
 * 预订记录 3 ：       25  25  25  25
 * <p>
 * 总座位数：      10  55  45  25  25
 * <p>
 * 因此，answer = [10,55,45,25,25]
 * <p>
 * 示例 2：
 * <p>
 * 输入：bookings = [[1,2,10],[2,2,15]], n = 2
 * 输出：[10,25]
 * 解释：
 * <p>
 * 航班编号        1   2
 * <p>
 * 预订记录 1 ：   10  10
 * <p>
 * 预订记录 2 ：       15
 * <p>
 * 总座位数：      10  25
 * <p>
 * 因此，answer = [10,25]
 *
 * @author caijinnan
 */
public class Day31_航班预订统计 {


    @Test
    public void run() {
        int[][] bookings = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
        int n = 5;
        System.out.println(Arrays.toString(corpFlightBookings(bookings, n)));
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] result = new int[n];
        for (int[] booking : bookings) {
            int first = booking[0];
            int last = booking[1];
            int seat = booking[2];
            result[first - 1] += seat;
            if (last < n) {
                result[last] -= seat;
            }
        }
        for (int i = 1; i < result.length; i++) {
            result[i] += result[i - 1];
        }
        return result;
    }

    /**
     * 差分数组对应的概念是前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，
     * 差分数组的第 i 个数即为原数组的第 i-1 个元素和第 i 个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组。
     *
     * 差分数组的性质是，当我们希望对原数组的某一个区间 [l,r] 施加一个增量inc 时，
     * 差分数组 d 对应的改变是：d[l] 增加 inc，d[r+1] 减少 inc。这样对于区间的修改就变为了对于两个位置的修改。并且这种修改是可以叠加的，
     * 即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。
     *
     */
    public int[] corpFlightBookingsTest(int[][] bookings, int n) {
        // 以 前一个为标准,统计差值数组;那么,对于区间内所有数进行增量时,对起始位增加,对中止位进行减少
        int[] counters = new int[n];
        for (int[] booking : bookings) {
            counters[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                counters[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; ++i) {
            counters[i] += counters[i - 1];
        }
        return counters;
    }


}
